{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16.3 Huffman codes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-1\n",
    "\n",
    "> Explain why, in the proof of Lemma 16.2, if $x.freq = b.freq$, then we must have $a.freq = b.freq = x.freq = y.freq$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-2\n",
    "\n",
    "> Prove that a binary tree that is not full cannot correspond to an optimal prefix code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-3\n",
    "\n",
    "> What is an optimal Huffman code for the following set of frequencies, based on\n",
    "the first 8 Fibonacci numbers? \n",
    "\n",
    "> a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21 \n",
    "\n",
    "> Can you generalize your answer to find the optimal code when the frequencies are the first $n$ Fibonacci numbers?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* a: 1111111\n",
    "* b: 1111110\n",
    "* c: 111110\n",
    "* d: 11110\n",
    "* e: 1110\n",
    "* f: 110\n",
    "* g: 10\n",
    "* h: 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-4\n",
    "\n",
    "> Prove that we can also express the total cost of a tree for a code as the sum, over all internal nodes, of the combined frequencies of the two children of the node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-5\n",
    "\n",
    "> Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-6\n",
    "\n",
    "> Suppose we have an optimal prefix code on a set $C = \\{0, 1, \\dots, n - 1\\}$ of characters and we wish to transmit this code using as few bits as possible. Show how to represent any optimal prefix code on $C$ using only $2n - 1 + n \\lceil lg n \\rceil$ bits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use one bit for representing internal or leaf node, which is $2n - 1$ bits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-7\n",
    "\n",
    "> Generalize Huffman’s algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge three nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-8\n",
    "\n",
    "> Suppose that a data file contains a sequence of 8-bit characters such that all 256 characters are about equally common: the maximum character frequency is less than twice the minimum character frequency. Prove that Huffman coding in this case is no more efficient than using an ordinary 8-bit fixed-length code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Full binary tree, another 8-bit encoding."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.3-9\n",
    "\n",
    "> Show that no compression scheme can expect to compress a file of randomly chosen 8-bit characters by even a single bit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$2^n >> 2^{n-1}$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
